# 冒泡
# class Solution:
#     def bubbleSort(self, nums: [int]) -> [int]:
#         for i in range(len(nums)-1):
#             flag = False
#             for j in range(len(nums)-i-1):
#                 if nums[j] > nums[j+1]:
#                     tmp = 0
#                     tmp = nums[j] 
#                     nums[j] = nums[j+1]
#                     nums[j+1] = tmp
#                     flag = True
#             if not flag:
#                 break
#         return nums
    
# sol = Solution()

# nums = [5,2,3,6,1,4]

# print(sol.bubbleSort(nums))



# 选择
# class Solution:
#     def SelectionSort(self, nums):
#         for i in range(len(nums)-1):
#             min_i = i
#             for j in range(i+1, len(nums)):
#                 if nums[j] < nums[min_i]:
#                     min_i = j
#             if i != min_i:
#                 tmp = 0
#                 tmp = nums[i]
#                 nums[i] = nums[min_i]
#                 nums[min_i] = tmp
#         return nums

# sol = Solution()

# nums = [5,2,3,6,1,4]

# print(sol.SelectionSort(nums))


# 插入
class Solution:
    def insertionSort(self, nums):
        for i in range(1, len(nums)):
            tmp = nums[i]
            j = i
            while j > 0 and nums[j-1] > tmp:
                nums[j] = nums[j-1]
                j -= 1
            nums[j] = tmp
        
        return nums
    
sol = Solution()

nums = [5,2,3,6,1,4]

print(sol.insertionSort(nums))


#希尔
class Solution:
    def shell(self, nums):
        size = len(nums)
        gap = size // 2
        while gap > 0:
            for i in range(gap,size):
                tmp = nums[i]
                j = 1
                while j >= gap and nums[j-gap] > tmp:
                    nums[j] = nums[j-gap]
                    


